package main

func main() {

}

type juchitreeNode struct {
	val   int
	left  *juchitreeNode
	right *juchitreeNode
}

func juchitraverseTree(root *juchitreeNode) [][]int {
	var ret [][]int
	q := []*juchitreeNode{root}
	k := len(ret)
	isRev := false
	if len(q) > 0 {
		curQue := []*juchitreeNode{}
		curRet := []int{}
		if k >= len(ret) {
			ret = append(ret, []int{})
		}
		for _, v := range q {
			curRet = append(curRet, v.val)
			if v.left != nil {
				curQue = append(curQue, v.left)
			}
			if v.right != nil {
				curQue = append(curQue, v.right)
			}
		}

		if isRev {
			revArr(curRet)
		}
		isRev = !isRev

		ret[k] = curRet
		q = curQue
		k++
	}

	return ret
}

func revArr(arr []int) {
	for i := 0; i < len(arr)/2; i++ {
		arr[i], arr[len(arr)-1-i] = arr[len(arr)-1-i], arr[i]
	}
}
